package com.lims.algorithm.algset.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * <功能简述>
 *
 * @author lims
 * @date 2020-04-22 11:11
 */
public class AVLTree<T extends Comparable<T>> {
    public static class AVLNode<T extends Comparable<T>> {
        T key;
        AVLNode<T> left;
        AVLNode<T> right;
        // 结点高度
        int height;

        public AVLNode(T key, AVLNode<T> left, AVLNode<T> right) {
            this.key = key;
            this.left = left;
            this.right = right;
            // 每次插入叶子节点，高度都是1
            this.height = 1;
        }
    }

    /**
     * 根结点
     */
    private AVLNode<T> avlRoot;

    /**
     * 结点高度
     *
     * @param avlNode
     * @return
     */
    private int getHeight(AVLNode<T> avlNode) {
        if (avlNode == null) {
            return 0;
        } else {
            return avlNode.height;
        }
    }

    /**
     * 获取结点的平衡因子
     */
    public int getBalanceFactor(AVLNode<T> avlNode) {
        if (avlNode == null) {
            return 0;
        }
        return getHeight(avlNode.left) - getHeight(avlNode.right);
    }


    /***********************************/
    /**
     * 检查二分搜索树性质和平衡性
     */
    /***********************************/
    /**
     * 检查是否为一个二叉查找树（中序遍历为升序）
     */
    public boolean isBsT() {
        ArrayList<T> keys = new ArrayList<>();
        inOrderAddList(avlRoot, keys);
        for (int i = 0; i < keys.size() - 1; i++) {
            if (keys.get(i).compareTo(keys.get(i + 1)) > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 中序遍历二叉树并key加入list
     */
    public void inOrderAddList(AVLNode<T> avlNode, List<T> keys) {
        if (avlNode == null) {
            return;
        }
        inOrderAddList(avlNode.left, keys);
        keys.add(avlNode.key);
        inOrderAddList(avlNode.right, keys);
    }

    /**
     * 判断是否平衡
     *
     * @return
     */
    public boolean isBalanced() {
        return isBalanced(avlRoot);
    }

    private boolean isBalanced(AVLNode<T> avlNode) {
        if (avlNode == null) {
            return true;
        }
        // 平衡因子
        int isBalanced = getBalanceFactor(avlNode);
        if (Math.abs(isBalanced) > 1) {
            return false;
        }
        return isBalanced(avlNode.left) &&
                isBalanced(avlNode.right);
    }

    /**
     * RR情况平衡（单左旋转）
     * <p>
     * *       oldNode                      newNode
     * *       /      \                    /       \
     * *      H     newNode    -->>     oldNode    H+1
     * *              /   \             /    \
     * *             H    H+1          H      H
     * *
     *
     * @param oldNode
     * @return
     */
    private AVLNode<T> goBalanceRR(AVLNode<T> oldNode) {
        // 对oldNode结点进行左旋
        AVLNode<T> newNode = oldNode.left;
        oldNode.right = newNode.left;
        newNode.left = oldNode;

        //重新计算oldNode和newNode高度（自己加左右子树高度）
        oldNode.height = 1 + Math.max(getHeight(oldNode.left), getHeight(oldNode.right));
        newNode.height = 1 + Math.max(getHeight(newNode.left), getHeight(newNode.right));

        return newNode;
    }

    /**
     * LL情况平衡（单右旋转）
     * <p>
     * *      oldNode                    newNode
     * *      /      \                  /       \
     * *   newNode    H      -->>     H+1      oldNode
     * *    /   \                              /    \
     * *  H+1    H                            H      H
     * *
     *
     * @param oldNode
     */
    private AVLNode<T> goBalanceLL(AVLNode<T> oldNode) {
        // 对oldNode结点进行右旋
        AVLNode<T> newNode = oldNode.left;
        oldNode.left = newNode.right;
        newNode.right = oldNode;

        //重新计算oldNode和newNode高度
        oldNode.height = 1 + Math.max(getHeight(oldNode.left), getHeight(oldNode.right));
        newNode.height = 1 + Math.max(getHeight(newNode.left), getHeight(newNode.right));

        return newNode;
    }

    /**
     * RL情况平衡（先对root.right右旋转再对root左旋转）
     * RL为中间高度失衡
     * *
     * *     root                   root                       RL
     * *   /     \                /     \                    /    \
     * *  H       R             H        RL                root    R
     * *        /   \    -->>           /  \     -->>     /   \   / \
     * *      RL     H                 A    R            H    A  B   H
     * *     /  \                          / \
     * *    A   B                         B   H
     * *
     *
     * @param oldNode
     */
    private AVLNode<T> goBalanceRL(AVLNode<T> oldNode) {
        // 先对LL情况的root.right进行右旋（右旋方法自动更新变化结点高度）
        oldNode.right = goBalanceLL(oldNode.right);
        // root的高度发生变化，更新高度
        oldNode.height = 1 + Math.max(getHeight(oldNode.left), getHeight(oldNode.right));
        // 对RR情况的root进行左旋，左旋方法对变化高度结点的高度自动更新
        AVLNode<T> newNode = goBalanceRR(oldNode);
        return newNode;
    }

    /**
     * LR情况平衡（先对root.left左旋转再root右旋转）
     * LR为中间高度失衡
     * *
     * *          root                 root                 LR
     * *        /     \               /    \              /    \
     * *       L       H             LR     H            L     root
     * *     /  \          -->>     /  \        -->>    / \    /  \
     * *    H   LR                 L    B              H   A  B   H
     * *       /  \              /  \
     * *      A    B            H   A
     * *
     * *
     *
     * @param oldNode
     */
    private AVLNode<T> goBalanceLR(AVLNode<T> oldNode) {
        // 先对RR情况的root.left进行左旋（左旋方法自动更新变化结点高度）
        oldNode.left = goBalanceRR(oldNode.left);
        // root的高度发生变化，更新高度
        oldNode.height = 1 + Math.max(getHeight(oldNode.left), getHeight(oldNode.right));
        // 对LL情况的root进行右旋，右旋方法对变化高度结点的高度自动更新
        AVLNode<T> newNode = goBalanceLL(oldNode);
        return newNode;
    }

    /**
     * 平衡调整 (返回调整后的顶点)
     *
     * @param avlNode
     * @return
     */
    private AVLNode<T> balance(AVLNode<T> avlNode) {
        if (avlNode == null) {
            return null;
        }
        // 平衡因子 （左子高度 - 右子高度） 小于0：左侧大 * 大于0：右侧大
        int balanceFactor = getHeight(avlNode.left) - getHeight(avlNode.right);
        if (Math.abs(balanceFactor) <= 1) {
            // 不需要平衡调整
            return avlNode;
        } else if (balanceFactor < 0) {
            // 平衡因子小于0，右侧大
            if (getHeight(avlNode.right.left) <= getHeight(avlNode.right.right)) {
                // 右子的左子 高度 < 右子的右子 高度，RR
                AVLNode<T> balanceRRNode = goBalanceRR(avlNode);
                return balanceRRNode;
            } else {
                // 右子的左子 高度 > 右子的右子 高度，RL
                AVLNode<T> balanceRLNode = goBalanceRL(avlNode);
                return balanceRLNode;
            }
        } else {
            // 平衡因子大于0, 左侧大
            if (getHeight(avlNode.left.left) >= getHeight(avlNode.left.right)) {
                // 左子的左子 高度 > 左子的右子 高度，LL
                AVLNode<T> balanceLLNode = goBalanceLL(avlNode);
                return balanceLLNode;
            } else {
                // 左子的左子 高度 < 左子的右子 高度，LR
                AVLNode<T> balanceLRNode = goBalanceLR(avlNode);
                return balanceLRNode;
            }
        }
    }

    /**
     * 插入结点
     *
     * @param key
     */
    public void insertAvl(T key) {
        if (contains(key, avlRoot)) {
            System.out.println("二叉树已经存在key:" + key);
            return;
        }
        AVLNode<T> insertAvlNode = new AVLNode<>(key, null, null);
        avlRoot = insert(insertAvlNode, avlRoot);
    }

    public AVLNode<T> insert(AVLNode<T> insertAvlNode, AVLNode<T> avlRoot) {
        if (avlRoot == null) {
            return insertAvlNode;
        } else {
            if (insertAvlNode.key.compareTo(avlRoot.key) < 0) {
                // 左子树
                avlRoot.left = insert(insertAvlNode, avlRoot.left);
            } else {
                // 右子树
                avlRoot.right = insert(insertAvlNode, avlRoot.right);
            }
        }
        avlRoot.height = 1 + Math.max(getHeight(avlRoot.left), getHeight(avlRoot.right));
        return balance(avlRoot);
    }

    /**
     * 查看是否存在
     *
     * @param key
     * @param avlNode
     * @return
     */
    public boolean contains(T key, AVLNode<T> avlNode) {
        if (avlNode == null) {
            return false;
        }
        if (key.compareTo(avlNode.key) == 0) {
            return true;
        }
        boolean leftFlag = contains(key, avlNode.left);
        boolean rightFlag;
        if (leftFlag) {
            return true;
        } else {
            rightFlag = contains(key, avlNode.right);
        }
        return rightFlag;
    }

    /**
     * 搜索结点
     *
     * @param key
     * @param avlNode
     * @return
     */
    public AVLNode<T> search(T key, AVLNode<T> avlNode) {
        if (avlNode == null) {
            return null;
        }
        if (key.compareTo(avlNode.key) == 0) {
            return avlNode;
        }
        AVLNode<T> searchNode = search(key, avlNode.left);
        AVLNode<T> searchRightNode;
        if (searchNode != null) {
            return searchNode;
        } else {
            searchRightNode = search(key, avlNode.right);
        }
        if (searchRightNode != null) {
            return searchRightNode;
        }
        return null;
    }

    /**
     * 先序遍历
     */
    public void preOrderRecur() {
        preOrderRecur(avlRoot);
    }

    private void preOrderRecur(AVLNode<T> avlNode) {
        if (avlNode == null) {
            return;
        }
        System.out.print(avlNode.key + " ");
        preOrderRecur(avlNode.left);
        preOrderRecur(avlNode.right);
    }

    /**
     * 中序遍历
     */
    public void inOrderRecur() {
        inOrderRecur(avlRoot);
    }

    private void inOrderRecur(AVLNode<T> avlNode) {
        if (avlNode == null) {
            return;
        }
        inOrderRecur(avlNode.left);
        System.out.print(avlNode.key + " ");
        inOrderRecur(avlNode.right);
    }

    /**
     * 后序遍历
     */
    public void postOrderRecur() {
        postOrderRecur(avlRoot);
    }

    private void postOrderRecur(AVLNode<T> avlNode) {
        if (avlNode == null) {
            return;
        }
        postOrderRecur(avlNode.left);
        postOrderRecur(avlNode.right);
        System.out.print(avlNode.key + " ");
    }

    /**
     * 查找最大值
     *
     * @return
     */
    public T findMax() {
        AVLNode<T> maximum = findMax(this.avlRoot);
        if (maximum != null) {
            return maximum.key;
        }
        return null;
    }

    /**
     * 查找最大结点：返回tree为根结点的二叉树的最大结点。
     *
     * @param avlRoot
     * @return
     */
    private AVLNode<T> findMax(AVLNode<T> avlRoot) {
        if (avlRoot == null) {
            return null;
        }
        while (avlRoot.right != null) {
            avlRoot = avlRoot.right;
        }
        return avlRoot;
    }

    /**
     * 查找最小值
     *
     * @return
     */
    public T findMin() {
        AVLNode<T> minimum = findMin(this.avlRoot);
        if (minimum != null) {
            return minimum.key;
        }
        return null;
    }

    /**
     * 查找最小结点：返回tree为根结点的二叉树的最大结点。
     *
     * @param avlRoot
     * @return
     */
    private AVLNode<T> findMin(AVLNode<T> avlRoot) {
        if (avlRoot == null) {
            return null;
        }
        while (avlRoot.left != null) {
            avlRoot = avlRoot.left;
        }
        return avlRoot;
    }

    /**
     * 删除结点
     *
     * @param key
     */
    public void remove(T key) {
        AVLNode<T> searchNode = search(key, avlRoot);
        if (searchNode == null) {
            System.out.println("没有找到删除结点key:" + key);
            return;
        }
        remove(searchNode, avlRoot);
    }

    private AVLNode<T> remove(AVLNode<T> delNode, AVLNode<T> avlRoot) {
        // 根为空 或者 没有要删除的节点，直接返回null。
        if (avlRoot == null || delNode == null) {
            return null;
        }
        // 待删除结点和根结点大小
        int cmp = delNode.key.compareTo(avlRoot.key);
        if (cmp < 0) {
            // 左子树中删除
            avlRoot.left = remove(delNode, avlRoot.left);
        } else if (cmp > 0) {
            // 右子树中删除
            avlRoot.right = remove(delNode, avlRoot.right);
        } else if (avlRoot.left != null &&
                avlRoot.right != null) {
            // 取出右子树中最小值，赋值给删除结点，并递归删除右子树那个最小值
            AVLNode<T> minRightNode = findMin(avlRoot.right);
            avlRoot.key = minRightNode.key;
            avlRoot.right = remove(minRightNode, avlRoot.right);
        } else {
            // 待删除结点只有一个子树时直接用子树代替，无子树时null代替
            avlRoot = (avlRoot.left != null ? avlRoot.left : avlRoot.right);
        }
        return balance(avlRoot);
    }


    /******************************分割线********************************/

    public static void main(String[] args) {
        AVLTree<Integer> avlTree = new AVLTree<>();

        avlTree.insertAvl(9);
        System.out.println("插入9时先序遍历");
        avlTree.preOrderRecur();
        System.out.println();

        avlTree.insertAvl(8);
        System.out.println("插入8时先序遍历");
        avlTree.preOrderRecur();
        System.out.println();

        avlTree.insertAvl(7);
        System.out.println("插入7时先序遍历");
        avlTree.preOrderRecur();
        System.out.println();

        avlTree.insertAvl(6);
        System.out.println("插入6时先序遍历");
        avlTree.preOrderRecur();
        System.out.println();

        avlTree.insertAvl(5);
        System.out.println("插入5时先序遍历");
        avlTree.preOrderRecur();
        System.out.println();

        avlTree.insertAvl(4);
        System.out.println("插入4时先序遍历");
        avlTree.preOrderRecur();
        System.out.println();

        avlTree.insertAvl(3);
        System.out.println("插入3时先序遍历");
        avlTree.preOrderRecur();
        System.out.println();

        avlTree.insertAvl(2);
        System.out.println("插入2时先序遍历");
        avlTree.preOrderRecur();
        System.out.println();

        avlTree.insertAvl(1);
        System.out.println("插入1时先序遍历");
        avlTree.preOrderRecur();
        System.out.println();
        System.out.println("插入1时中序遍历");
        avlTree.inOrderRecur();
        System.out.println();
        System.out.println("插入1时后序遍历");
        avlTree.postOrderRecur();
        System.out.println();

        System.out.println("删除结点4");
        avlTree.remove(4);
        System.out.println("删除结点时先序遍历");
        avlTree.preOrderRecur();
        System.out.println();
        System.out.println("删除结点时中序遍历");
        avlTree.inOrderRecur();
        System.out.println();
        System.out.println("删除结点时后序遍历");
        avlTree.postOrderRecur();
        System.out.println();
        /************************************************/
        /**
         * *                   10
         * *                /      \
         * *               4       12
         * *            /    \     /  \
         * *           2      8   11  13
         * *         /  \   /  \       \
         * *        1   3  5   9       14
         * *               \
         * *               7
         *
         */
        AVLTree<Integer> avlTree2 = new AVLTree<>();

        avlTree2.insertAvl(10);
        avlTree2.insertAvl(4);
        avlTree2.insertAvl(12);
        avlTree2.insertAvl(2);
        avlTree2.insertAvl(8);
        avlTree2.insertAvl(11);
        avlTree2.insertAvl(13);
        avlTree2.insertAvl(1);
        avlTree2.insertAvl(3);
        avlTree2.insertAvl(5);
        avlTree2.insertAvl(9);
        avlTree2.insertAvl(14);
        avlTree2.insertAvl(7);

        System.out.println("先序遍历");
        avlTree2.preOrderRecur();
        System.out.println();
        System.out.println("中序遍历");
        avlTree2.inOrderRecur();
        System.out.println();
        System.out.println("后序遍历");
        avlTree2.postOrderRecur();
        System.out.println();

        System.out.println("删除结点4");
        avlTree2.remove(4);
        System.out.println("删除结点时先序遍历");
        avlTree2.preOrderRecur();
        System.out.println();
        System.out.println("删除结点时中序遍历");
        avlTree2.inOrderRecur();
        System.out.println();
        System.out.println("删除结点时后序遍历");
        avlTree2.postOrderRecur();
        System.out.println();
    }
}
